package com.example.system.class13;

/**
 * @Date 2022/8/1
 * @Author Jonathan
 * @Description 是否是二叉搜索树
 * 二叉搜索树：左孩子 < 根节点 < 右孩子
 */
public class Code03_IsBST {
    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, null, 4, 3, null, null, 9, null, null};
        System.out.println("isBST:" + getResult(createBST(arr)));
        index = 0;
        arr = new Integer[]{7, 6, 3, null, null, null, 9, 8, null, null, 10, null, null};
        System.out.println("isBST:" + getResult(createBST(arr)));
        //      7
        //     / \
    }

    public static boolean getResult(Node root) {
        return process(root).isBST;
    }

    private static Info process(Node x) {
        // base case
        if (x == null) {
            return null;
        }
        Info left = process(x.left);
        Info right = process(x.right);
        // 因为base case里面返回null  因此这里需要对null进行判断
        // 都不为null
        if (left != null && right != null) {
            int max = Math.max(left.max, right.max);
            int min = Math.min(left.min, right.min);
            // 左边是  右边是
            boolean isBst = left.isBST && right.isBST && left.max <= x.value && x.value <= right.min;
            return new Info(min, max, isBst);
        }
        if (left != null) {
            int max = Math.max(left.max, x.value);
            int min = Math.min(left.min, x.value);
            // 左边是  右边是
            boolean isBst = left.isBST && left.max <= x.value;
            return new Info(min, max, isBst);
        }

        if (right != null) {
            int max = Math.max(right.max, x.value);
            int min = Math.min(right.min, x.value);
            // 左边是  右边是
            boolean isBst = right.isBST && right.min >= x.value;
            return new Info(min, max, isBst);
        }
        return new Info(x.value, x.value, true);
    }


    static class Info {
        private int min;
        private int max;
        private boolean isBST;

        public Info(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }


    public static Node createBST(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        //System.out.printf("index:%d, arr[index]:%d\n", index, value);
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }
}
